<!DOCTYPE html><html><head>
<title>grammar::me_ast - Grammar operations and usage</title>
<style type="text/css"><!--
    HTML {
	background: 	#FFFFFF;
	color: 		black;
    }
    BODY {
	background: 	#FFFFFF;
	color:	 	black;
    }
    DIV.doctools {
	margin-left:	10%;
	margin-right:	10%;
    }
    DIV.doctools H1,DIV.doctools H2 {
	margin-left:	-5%;
    }
    H1, H2, H3, H4 {
	margin-top: 	1em;
	font-family:	sans-serif;
	font-size:	large;
	color:		#005A9C;
	background: 	transparent;
	text-align:		left;
    }
    H1.doctools_title {
	text-align: center;
    }
    UL,OL {
	margin-right: 0em;
	margin-top: 3pt;
	margin-bottom: 3pt;
    }
    UL LI {
	list-style: disc;
    }
    OL LI {
	list-style: decimal;
    }
    DT {
	padding-top: 	1ex;
    }
    UL.doctools_toc,UL.doctools_toc UL, UL.doctools_toc UL UL {
	font:		normal 12pt/14pt sans-serif;
	list-style:	none;
    }
    LI.doctools_section, LI.doctools_subsection {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding: 	0em;
    }
    PRE {
	display: 	block;
	font-family:	monospace;
	white-space:	pre;
	margin:		0%;
	padding-top:	0.5ex;
	padding-bottom:	0.5ex;
	padding-left:	1ex;
	padding-right:	1ex;
	width:		100%;
    }
    PRE.doctools_example {
	color: 		black;
	background: 	#f5dcb3;
	border:		1px solid black;
    }
    UL.doctools_requirements LI, UL.doctools_syntax LI {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding:	0em;
    }
    DIV.doctools_synopsis {
	color: 		black;
	background: 	#80ffff;
	border:		1px solid black;
	font-family:	serif;
	margin-top: 	1em;
	margin-bottom: 	1em;
    }
    UL.doctools_syntax {
	margin-top: 	1em;
	border-top:	1px solid black;
    }
    UL.doctools_requirements {
	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<!-- Generated from file 'me_ast.man' by tcllib/doctools with format 'html'
   -->
<!-- Copyright &amp;copy; 2005 Andreas Kupries &amp;lt;andreas_kupries@users.sourceforge.net&amp;gt;
   -->
<!-- grammar::me_ast.n
   -->
<body><hr> [
   <a href="../../../../../../../../home">Tcllib Home</a>
&#124; <a href="../../../../toc.html">Main Table Of Contents</a>
&#124; <a href="../../../toc.html">Table Of Contents</a>
&#124; <a href="../../../../index.html">Keyword Index</a>
&#124; <a href="../../../../toc0.html">Categories</a>
&#124; <a href="../../../../toc1.html">Modules</a>
&#124; <a href="../../../../toc2.html">Applications</a>
 ] <hr>
<div class="doctools">
<h1 class="doctools_title">grammar::me_ast(n) 0.1 tcllib &quot;Grammar operations and usage&quot;</h1>
<div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
<p>grammar::me_ast - Various representations of ASTs</p>
</div>
<div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="doctools_toc">
<li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
<li class="doctools_section"><a href="#section1">Description</a></li>
<li class="doctools_section"><a href="#section2">AST VALUES</a></li>
<li class="doctools_section"><a href="#section3">AST OBJECTS</a></li>
<li class="doctools_section"><a href="#section4">EXTENDED AST OBJECTS</a></li>
<li class="doctools_section"><a href="#section5">Bugs, Ideas, Feedback</a></li>
<li class="doctools_section"><a href="#keywords">Keywords</a></li>
<li class="doctools_section"><a href="#category">Category</a></li>
<li class="doctools_section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="section1" class="doctools_section"><h2><a name="section1">Description</a></h2>
<p>This document specifies various representations for the
<i class="term"><a href="../../../../index.html#abstract_syntax_tree">abstract syntax tree</a></i>s (short <i class="term"><a href="../../../../index.html#ast">AST</a></i>) generated by
instances of ME virtual machines, independent of variant.
Please go and read the document <b class="syscmd"><a href="me_intro.html">grammar::me_intro</a></b> first if
you do not know what a ME virtual machine is.</p>
<p>ASTs and all the representations we specify distinguish between two
types of nodes, namely:</p>
<dl class="doctools_definitions">
<dt>Terminal</dt>
<dd><p>Terminal nodes refer to the terminal symbols found in the token
stream. They are always leaf nodes. I.e. terminal nodes never have
children.</p></dd>
<dt>Nonterminal</dt>
<dd><p>Nonterminal nodes represent a nonterminal symbol of the grammar used
during parsing. They can occur as leaf and inner nodes of the
tree.</p></dd>
</dl>
<p>Both types of nodes carry basic range information telling a user which
parts of the input are covered by the node by providing the location
of the first and last tokens found within the range. Locations are
provided as non-negative integer offsets from the beginning of the
token stream, with the first token found in the stream located at
offset 0 (zero).</p>
<p>The root of an AS tree can be either a terminal or nonterminal node.</p>
</div>
<div id="section2" class="doctools_section"><h2><a name="section2">AST VALUES</a></h2>
<p>This representation of ASTs is a Tcl list. The main list represents
the root node of the tree, with the representations of the children
nested within.</p>
<p>Each node is represented by a single Tcl list containing three or more
elements. The first element is either the empty string or the name of
a nonterminal symbol (which is never the empty string). The second and
third elements are then the locations of the first and last tokens.
Any additional elements after the third are then the representations
of the children, with the leftmost child first, i.e. as the fourth
element of the list representing the node.</p>
</div>
<div id="section3" class="doctools_section"><h2><a name="section3">AST OBJECTS</a></h2>
<p>In this representation an AST is represented by a Tcl object command
whose API is compatible to the tree objects provided by the package
<b class="package"><a href="../struct/struct_tree.html">struct::tree</a></b>. I.e it has to support at least all of the
methods described by that package, and may support more.</p>
<p>Because of this the remainder of the specifications is written using
the terms of <b class="package"><a href="../struct/struct_tree.html">struct::tree</a></b>.</p>
<p>Each node of the AST directly maps to a node in the tree object. All
data beyond the child nodes, i.e. node type and input locations, are
stored in attributes of the node in the tree object. They are:</p>
<dl class="doctools_definitions">
<dt>type</dt>
<dd><p>The type of the AST node. The recognized values are <b class="const">terminal</b>
and <b class="const">nonterminal</b>.</p></dd>
<dt>range</dt>
<dd><p>The locations of the first and last token of the terminal data in the
input covered by the node. This is a list containing two locations.</p></dd>
<dt>detail</dt>
<dd><p>This attribute is present only for nonterminal nodes. It contains the
name of the nonterminal symbol stored in the node.</p></dd>
</dl>
</div>
<div id="section4" class="doctools_section"><h2><a name="section4">EXTENDED AST OBJECTS</a></h2>
<p>Extended AST objects are like AST objects, with additional
information.</p>
<dl class="doctools_definitions">
<dt>detail</dt>
<dd><p>This attribute is now present at all nodes. Its contents are unchanged
for nonterminal nodes. For terminal nodes it contains a list
describing all tokens from the input which are covered by the node.</p>
<p>Each element of the list contains the token name, the associated
lexeme attribute, line number, and column index, in this order.</p></dd>
<dt>range_lc</dt>
<dd><p>This new attribute is defined for all nodes, and contains the
locations from attribute <i class="term">range</i> translated into line number and
column index. Lines are counted from 1, columns are counted from 0.</p></dd>
</dl>
</div>
<div id="section5" class="doctools_section"><h2><a name="section5">Bugs, Ideas, Feedback</a></h2>
<p>This document, and the package it describes, will undoubtedly contain
bugs and other problems.
Please report such in the category <em>grammar_me</em> of the
<a href="http://core.tcl.tk/tcllib/reportlist">Tcllib Trackers</a>.
Please also report any ideas for enhancements you may have for either
package and/or documentation.</p>
<p>When proposing code changes, please provide <em>unified diffs</em>,
i.e the output of <b class="const">diff -u</b>.</p>
<p>Note further that <em>attachments</em> are strongly preferred over
inlined patches. Attachments can be made by going to the <b class="const">Edit</b>
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar.</p>
</div>
<div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
<p><a href="../../../../index.html#ast">AST</a>, <a href="../../../../index.html#abstract_syntax_tree">abstract syntax tree</a></p>
</div>
<div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
<p>Grammars and finite automata</p>
</div>
<div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2005 Andreas Kupries &lt;andreas_kupries@users.sourceforge.net&gt;</p>
</div>
</div></body></html>
